/*!
 * \file graph.h
 *
 * \date Sep 24, 2013
 * \author Ricardo C. Corrêa (correa@lia.ufc.br)
 *
 * \brief Macros and inline functions of a bitmap implementation of a graph adjacency matrix.
 */

#ifndef GRAPH_H_
#define GRAPH_H_

#include <stdlib.h>
#include <string.h>
#include <bitmap.h>
#include <malloc.h>

/*!
 * \struct Graph
 * \brief Bitmap implementation of a graph adjacency matrix.
 *
 * In order to optimize indexing, the number of nodes in a row is augmented up to a power of 2.
 */
typedef struct {
	size_t n; //!< Number of vertices
	size_t m; //!< Number of edges
	BitMap * matrix; //!< Bitmap adjacency matrix.
	size_t matrixsize; //!< Of the bitmap, in bytes.
	size_t logrowsize; //!< Logarithmic of the row's number of nodes.
	int maxcq; //!< Size of the maximum clique.
	double maxwcq; //!< Weight o the maximum clique.
} Graph;

#define ROWINDEX(g,i) ((i) << g->logrowsize)								//!< Index in the bitmap \c g of the first element in row \c i.
#define PAIRINDEX(g, i, j) (ROWINDEX(g,i)+NODEIDX(j))						//!< Index in the bitmap \c g of the edge \c i, \c j.
#define ADDEDGE(g, i, j) ADDTONODE(NEIG(g,i)[NODEIDX(j)],IDXINNODE(j))		//!< Returns the node of \c g containing the edge \c i, \c j.
#define DELEDGE(g, i, j) DELFROMNODE(NEIG(g,i)[NODEIDX(j)],IDXINNODE(j))	//!< Returns the node of \c g with the edge \c i, \c j unset.

static inline int inline_ceillog2(int n) {
	int c = 0;
	int l = 0;
	while (n > 1) {
		c |= (n & 1);
		n >>= 1;
		l++;
	}
	l += c;
	return l;
}

/*!
 * \fn Graph * newGraph(size_t n)
 * \brief Creates a new graph with the specified number of vertices and with no edges.
 *
 * \param n The number of vertices.
 *
 * \return The bitmap implementation of the graph.
 */
//Graph * newGraph(size_t n);
static inline Graph * newGraph(size_t n) {
	Graph * ret = (Graph *) malloc(sizeof(Graph));
	ret->logrowsize = (inline_ceillog2(n) - LOGB);
	if (ret->logrowsize < 0)
		ret->logrowsize = 0;
	ret->matrixsize = ((1 << ret->logrowsize) * n) << LOGW;
	ret->n = n;
	ret->matrix = (NODETYPE *) malloc(ret->matrixsize);
	memset(ret->matrix, 0, ret->matrixsize);

	return ret;
}

/*!
 * \fn void delGraph(Graph * g)
 * \brief Deletes the bitmap associated with the specified graph.
 *
 * \param g The graph.
 */
//void delGraph(Graph * g);
static inline void delGraph(Graph * g) {
	printf("g-matrix=%d\n",g->matrix);
	freeBitMap(g->matrix);
	free(g->matrix);
}

//static inline Graph * newRenumbered(Graph * gg, int * R) {
//	int n = gg->n;
//	int nnodes = NODEIDX(n-1) + 1;
//
//	Graph * g = newGraph(n);
//
//	int i, j, k, l;
//	for (i = 0; i < n; i++) {
//		NODETYPE * ignode = NEIG(g,R[i]);
//		NODETYPE * iggnode = NEIG(gg,i);
//		k = NODEIDX(i);
//		j = NODENEXTLEAST(iggnode[k], IDXINNODE(i));
//		while (j >= 0) {
//			l = R[NELEM(k) + j];
//			ignode[NODEIDX(l)] = ADDTONODE(ignode[NODEIDX(l)],IDXINNODE(l));
//			NEIG(g,l)[NODEIDX(R[i])] =
//					ADDTONODE(NEIG(g,l)[NODEIDX(R[i])], IDXINNODE(R[i]));
//			j = NODENEXTLEAST(iggnode[k], j);
//		}
//		for (k++; k < nnodes; k++) {
//			j = NODELEAST(iggnode[k]);
//			while (j >= 0) {
//				l = R[NELEM(k) + j];
//				ignode[NODEIDX(l)] = ADDTONODE(ignode[NODEIDX(l)],IDXINNODE(l));
//				NEIG(g,l)[NODEIDX(R[i])] =
//						ADDTONODE(NEIG(g,l)[NODEIDX(R[i])], IDXINNODE(R[i]));
//				j = NODENEXTLEAST(iggnode[k], j);
//			}
//		}
//	}
//
//	return g;
//}

//!< Bitmap corresponding to the neigborhood of \c i in \c g.
static inline BitMap const * neig(Graph * g, int i) {
	g->matrix->minRNode = g->matrix->R+ROWINDEX(g,i);
	g->matrix->maxRNode = g->matrix->minRNode+(1LL << g->logrowsize);
	return g->matrix;
}

//!< Returns a non-zero value if \c i, \c j defines an edge in \c g, and 0 otherwise.
static inline int hasEdge(Graph * g, int i, int j) {
	return hasElement(neig(g, i), j);
}

#ifdef _DEBUG_
static inline void printNeigNodes(Graph * g, int i) {
	int lastnode = NODEIDX(g->n-1);
	int node;

	printf("NEIG(%d): [",i);
	for (node = lastnode; node >= 0; node--)
	printf(FORMX, NEIG(g,i)[node]);
	printf("]\n");
}

static inline void printNodes(Graph * g) {
	int i;
	for (i = 0; i < g->n; i++)
	printNeigNodes(g, i);
}
#endif

#endif /* GRAPH_H_ */
